#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/11 17:55
# ===========================================
#       题目名称： 88. 合并两个有序数组
#       题目地址： https://leetcode.cn/problems/merge-sorted-array/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================

class Solution:
    def merge(self, nums1, m, nums2, n):
        """
            谁大谁先走
        """
        cur_index = len(nums1) - 1
        while n > 0:
            if m > 0 and nums1[m - 1] > nums2[n - 1]:
                nums1[cur_index] = nums1[m - 1]
                nums1[m - 1] = 0
                m -= 1
            else:
                nums1[cur_index] = nums2[n - 1]
                n -= 1
            cur_index -= 1
        print(nums1)

    def merge2(self, nums1, m, nums2, n):
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # 先合并 再 排序
        for x in range(len(nums1)):
            if nums1[x] == 0 and n > 0:
                nums1[x] = nums2.pop()
        x, y = 0, 1
        while x < y < len(nums1):
            if nums1[x] > nums1[y]:
                nums1[x], nums1[y] = nums1[y], nums1[x]
            if y + 1 < len(nums1):
                y += 1
            else:
                if x + 1 > len(nums1) - 1:
                    break
                else:
                    x += 1
                    y = x + 1
        print(nums1)


if __name__ == '__main__':
    s = Solution()
    # [1,2,2,3,5,6]
    s.merge(nums1=[1, 2, 3, 0, 0, 0], m=3, nums2=[2, 5, 6], n=3)
    # [1]
    s.merge(nums1=[1], m=1, nums2=[], n=0)
    # [1]
    s.merge(nums1=[0], m=0, nums2=[1], n=1)
    # [1, 2]
    s.merge(nums1=[2, 0], m=1, nums2=[1], n=1)
